package main

import "sort"

func getSquares(n int) []int {
	var ret []int
	for i := 1; i*i <= n; i++ {
		ret = append(ret, i*i)
	}
	return ret
}

var mem = make(map[int]int) // sum -> numSquares

func recursive(n int, squares []int) int {
	if n == 0 {
		return 0
	}
	if n <= 3 {
		return n
	}
	if v, ok := mem[n]; ok {
		return v
	}
	end := sort.Search(len(squares), func(i int) bool {
		return squares[i] >= n
	})
	min := 99999
	if end >= len(squares) || squares[end] > n {
		end--
	}
	for i := end; i >= 0; i-- {
		v := squares[i]
		num := recursive(n-v, squares)
		if num < min {
			min = num
		}
	}
	mem[n] = min + 1
	return min + 1
}

func numSquares(n int) int {
	squares := getSquares(n)
	return recursive(n, squares)
}

func main() {

}
